package algorithms

import (
	"container/heap"
	"fmt"
	"math"
)

type GraphDijkstra struct {
	V   int      //顶点个数
	Adj [][]Edge //邻接矩阵
}

type Vertex struct {
	id   int
	dist int
}
//有向边
type Edge struct {
	sid, tid int
	w        int
}

func NewGraphDijkstra(v int) *GraphDijkstra {
	g := &GraphDijkstra{
		V:   v,
		Adj: make([][]Edge, v),
	}
	//初始化切片
	for i := 0; i < v; i++ {
		g.Adj[i] = []Edge{}
	}
	return g
}

//有向图添加边，s和t代表顶点
func (g *GraphDijkstra) AddEdge(s, t, w int) {
	g.Adj[s] = append(g.Adj[s], Edge{
		sid: s,
		tid: t,
		w:   w,
	})
}
//优先级队列
type PriorityQueue struct {
	nodes []Vertex
	count int
}

func NewPriorityQueue(v int) *PriorityQueue {
	return &PriorityQueue{
		nodes: make([]Vertex, 0),
		count: v,
	}
}

func (p *PriorityQueue) Update(vertex Vertex) {
	for i := range p.nodes {
		if p.nodes[i].id == vertex.id {
			p.nodes[i].dist = vertex.dist
			return
		}
	}
}

func (p *PriorityQueue) Push(x interface{}) {
	p.nodes = append(p.nodes, x.(Vertex))
}

func (p *PriorityQueue) Pop() interface{} {
	x := p.nodes[len(p.nodes)-1]
	p.nodes = p.nodes[:len(p.nodes)-1]
	return x
}

func (p PriorityQueue) Len() int {
	return len(p.nodes)
}

func (p PriorityQueue) Less(i, j int) bool {
	return p.nodes[i].dist < p.nodes[j].dist
}

func (p PriorityQueue) Swap(i, j int) {
	p.nodes[i], p.nodes[j] = p.nodes[j], p.nodes[i]
}
//时间复杂度O(e*logv),logv是优先级队列的复杂度
//A*算法的区别是添加了一个和终点的曼哈顿距离作为判断因子
//而且搜索到终点直接结束，不会去寻求最值距离
func (g *GraphDijkstra) Dijkstra(s, t int) {
	//记录前驱结点
	predecessor:=make([]int, g.V)
	//优先级队列
	queue := NewPriorityQueue(g.V)
	//记录顶点有没有入队
	inqueue:=make([]bool,g.V)
	//图里顶点，记录dist信息
	vertexs := make([]Vertex, g.V)
	for i:=0;i<g.V;i++{
		vertexs[i]=Vertex{
			id:   i,
			dist: math.MaxInt32,
		}
	}
	//开始计算
	vertexs[s].dist=0
	queue.Push(vertexs[s])
	inqueue[s]=true
	for queue.Len()!=0{
		//取栈顶元素并删除
		minVertex := heap.Pop(queue).(Vertex)
		//找到最短路径
		if minVertex.id==t{
			break
		}
		for i:=0;i< len(g.Adj[minVertex.id]);i++{
			e:=g.Adj[minVertex.id][i]
			//更新该节点的dist值
			if minVertex.dist+e.w<vertexs[e.tid].dist{
				vertexs[e.tid].dist=minVertex.dist+e.w
				//将e.sid-->e.tid
				predecessor[e.tid]=e.sid
				if inqueue[e.tid]{
					queue.Update(vertexs[e.tid])
				}else {
					heap.Push(queue,vertexs[e.tid])
					inqueue[e.tid]=true
				}
			}
		}
	}
	fmt.Print(s)
	print(s,t,predecessor)
	fmt.Println()
}

func print(s,t int,predecessor []int)  {
	if s==t{
		return
	}
	print(s,predecessor[t],predecessor)
	fmt.Print("->",t)
}
